#pragma once

#include <iostream>
using namespace std;

typedef struct BinaryTreeNode {
    char data;
    BinaryTreeNode* LChild;
    BinaryTreeNode* RChild;

    //是否被访问过
    bool isCall = false;
}BrinaryNode;

//前序遍历方式创建树
void CreateBinaryTree(BinaryTreeNode** T) {
    char data;
    cin >> data;
    if (data != '#') {
        *T = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
        (*T)->data = data;
        CreateBinaryTree(&(*T)->LChild);
        CreateBinaryTree(&(*T)->RChild);
    }

    else {
        *T = nullptr;
    }
}
//前序遍历方式创建树, 读取字符串
void CreateBinaryTree(BinaryTreeNode** T, const char* data, int* index) {
    char ch;
    ch = data[*index];
    *index += 1;
    if (ch != '#') {
        *T = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
        (*T)->data = ch;
        CreateBinaryTree(&(*T)->LChild, data, index);
        CreateBinaryTree(&(*T)->RChild, data, index);
    }

    else {
        *T = NULL;
    }
}

//二叉树前序遍历
void PreTravelBinaryTree(BinaryTreeNode* T) {
    if (T != NULL) {
        cout << T->data << " ";
        PreTravelBinaryTree(T->LChild);
        PreTravelBinaryTree(T->RChild);
    }
}

//二叉树中序遍历
void InTravelBinaryTree(BinaryTreeNode* T) {
    if (T != NULL) {
        InTravelBinaryTree(T->LChild);
        cout << T->data << " ";
        InTravelBinaryTree(T->RChild);
    }
}

//二叉树后序遍历
void BackTravelBinaryTree(BinaryTreeNode* T) {
    if (T != NULL) {
        BackTravelBinaryTree(T->LChild);
        BackTravelBinaryTree(T->RChild);
        cout << T->data << " ";
    }
}